Tương truyền khi đào đất đắp thành Thăng Long vào đời vua Lê Thánh Tông (1460 - 1497) ở làng Báo Thiên Tự Tháp (khu vực Nhà thờ Lớn ngày nay) thì phát hiện được một pho tượng bằng đá hình dáng một phụ nữ (có thuyết cho là một pho tượng Phật Bà bằng đá). Dân chúng cho là thánh mẫu nên đã lập đền thờ ngay tại nơi đào được tượng và gọi là đền Bà Đá. Sau người làng thấy linh thiêng mới góp công, góp của xây thành chùa lớn, đón sư về trụ trì và thờ Phật. Vì vậy chùa có tên là chùa Bà Đá và tên chữ là "Linh Quang tự".

Khi quân Tây Sơn đánh ra Thăng Long , chùa đổ nát hoang tàn , Thiền Sư Khoan Giai bên chùa Hòe Nhai , dòng Tào Động bèn về trùng tu trụ trì .

Sang thời Pháp thuộc, đền bị cháy và pho tượng đá nguyên thủy bị hủy mất. Dân làng cho xây lại, rước một pho tượng Phật Thích Ca bằng đá về thờ, thay thế tượng Bà Đá cũ. Vì đã qua mấy đợt tu sửa, chùa Bà Đá không còn giữ được nhiều cổ vật. Lưu lại là một số di vật như hai quả chuông đúc vào triều Tự Đức nhà Nguyễn năm 1873 và năm 1881, và một tấm khánh đồng đúc năm 1842.

Ngày 5 tháng 1 năm 1946, Chủ tịch Hồ Chí Minh có đến thăm chùa Bà Đá và nói chuyện với các thượng tọa, tăng ni, Phật tử. Trong cuộc gặp, ông đã nói "Việc Phật không xa rời việc thế gian, phải tham gia vào các công việc cách mạng, cứu đói, cứu dốt".[cần dẫn nguồn]